Redis Bloom FIlter Pattern
ある要素が過去に追加されたことが無いかどうかを確認するためのデータ構造
偽陽性はあるが偽陰性はない
含まれていないのに含まれていると判定することがある
SISMEMBER よりもはるかにコンパクトで速い
アルゴリズム
mビットのビット配列とk個のハッシュ関数を用意する
アイテムを追加するには、アイテムをk個のハッシュ関数にいれてk個のindexをのビットを1にする
アイテムが集合に含まれるか調べるにはk個のハッシュ関数に入れる
どれかひとつでも0であれば集合に含まれていない
すべて1の場合は集合に含まれているか、たまたま他の要素を追加したときに全部1になった(偽陽性)
要素の削除はできない
用途の例
username が既に存在しているものかどうか調べる
GETBIT, SETBIT で古くから実装されてきた
ReBloom module が利用できる (>=Redis 4.0)
code:sh
BF.ADD usernames funnyfred
(integer) 1
BF.ADD usernames fredisfunny
(integer) 1
BF.ADD usernames fred
(integer) 1
BF.ADD usernames funfred
(integer) 1
BF.EXISTS usernames fred
(integer) 1
BF.EXISTS usernames fred_is_funny
(integer) 0
// check error rate and size
BF.RESERVE